package com.gitee.wsl.platform.thread.task.collection

import org.jetbrains.annotations.ApiStatus
import java.util.*
import java.util.function.Predicate


@ApiStatus.Internal
internal abstract class ImmutableStack<T> : Iterable<T> {
    fun prepend(value: T): ImmutableStack<T> {
        return ImmutableStack.Cons<T>(value, this)
    }

    fun prependAll(values: Iterable<T>): ImmutableStack<T> {
        var result: ImmutableStack<T> = this
        for (t in values) {
            result = result.prepend(t)
        }
        return result
    }

    fun head(): T? {
        if (this is Cons<*>) {
            return (this as Cons<T>).head
        } else {
            return null
        }
    }

    fun tail(): ImmutableStack<T>? {
        return if (this is Cons<*>) {
            (this as Cons<T>).tail
        } else {
            this
        }
    }

    val isEmpty: Boolean
        get() = this is Nil<*>

    fun reverse(): ImmutableStack<T> {
        var result = empty<T>()
        for (t in this) {
            result = result.prepend(t)
        }
        return result
    }

    internal class Cons<T>(val head: T?,
                           val tail: ImmutableStack<T>?
    ) : ImmutableStack<T>() {
        override fun equals(other: Any?): Boolean {
            if (other !is Cons<*>) return false
            return head == other.head && tail == other.tail
        }

        override fun hashCode(): Int {
            return Objects.hash(head, tail)
        }
    }

    internal class Nil<T> : ImmutableStack<T>() {
        override fun hashCode(): Int {
            return -2938
        }

        override fun equals(other: Any?): Boolean {
            return other is Nil<*>
        }
    }

    override fun iterator(): MutableIterator<T> {
        val start: ImmutableStack<T> = this
        return object : MutableIterator<T> {
            private var current: ImmutableStack<T> = start

            override fun hasNext(): Boolean {
                return current is Cons<*>
            }

            override fun next(): T {
                if (current is Cons<T>) {
                    current = (current as Cons<T>).tail!!
                    return current.head()!!
                } else {
                    throw NoSuchElementException()
                }
            }

            override fun remove() {
                TODO("Not yet implemented")
            }
        }
    }

    override fun toString(): String {
        val sb = StringBuilder()
        sb.append("ImmutableStack(")
        var isFirst = true
        for (t in this) {
            if (isFirst) {
                isFirst = false
            } else {
                sb.append(", ")
            }
            sb.append(t)
        }
        sb.append(")")
        return sb.toString()
    }

    companion object {
        fun <T> empty(): ImmutableStack<T> {
            return Nil<T>()
        }
    }
}

@ApiStatus.Internal
internal class ImmutableQueue<T> private constructor(
    private val toEnqueue: ImmutableStack<T>,
    private val toDequeue: ImmutableStack<T>,
) : Iterable<T> {
    fun enqueue(value: T): ImmutableQueue<T> {
        return ImmutableQueue(toEnqueue.prepend(value), toDequeue)
    }

    fun toList(): ImmutableStack<T> {
        return toEnqueue.reverse().prependAll(toDequeue.reverse())
    }

    fun preOptimize(): ImmutableQueue<T> {
        if (toDequeue.isEmpty) {
            return ImmutableQueue<T>(ImmutableStack.Companion.empty<T>(), toEnqueue.reverse())
        } else {
            return this
        }
    }

    @Throws(NoSuchElementException::class)
    fun peek(): T? {
        return if (!toDequeue.isEmpty) {
            toDequeue.head()
        } else if (!toEnqueue.isEmpty) {
            toEnqueue.reverse().head()
        } else {
            throw NoSuchElementException("peek() on empty queue")
        }
    }

    fun dequeue(): ImmutableQueue<T> {
        return if (!toDequeue.isEmpty) {
            ImmutableQueue(toEnqueue, toDequeue.tail()!!)
        } else if (!toEnqueue.isEmpty) {
            ImmutableQueue(ImmutableStack.empty<T>(), toEnqueue.reverse().tail()!!)
        } else {
            this
        }
    }

    val isEmpty: Boolean
        get() = toEnqueue.isEmpty && toDequeue.isEmpty

    fun filter(predicate: Predicate<in T>): ImmutableQueue<T> {
        var result = empty<T>()
        for (t in this) {
            if (predicate.test(t)) {
                result = result.enqueue(t)
            }
        }
        return result
    }

    override fun iterator(): MutableIterator<T> {
        return object : MutableIterator<T> {
            private var current: ImmutableQueue<T> = this@ImmutableQueue

            override fun hasNext(): Boolean {
                return !current.isEmpty
            }

            override fun next(): T {
                current = current.preOptimize()
                if (current.isEmpty) {
                    throw NoSuchElementException("next() on empty queue")
                }
                val value = current.peek()
                current = current.dequeue()
                return value!!
            }

            override fun remove() {
                TODO("Not yet implemented")
            }
        }
    }


    override fun toString(): String {
        val sb = StringBuilder()
        sb.append("ImmutableQueue(")
        var isFirst = true
        for (t in this) {
            if (isFirst) {
                isFirst = false
            } else {
                sb.append(", ")
            }
            sb.append(t)
        }
        sb.append(")")
        return sb.toString()
    }

    override fun equals(other: Any?): Boolean {
        if (other is ImmutableQueue<*>) {
            return toList() == other.toList()
        } else {
            return false
        }
    }

    override fun hashCode(): Int {
        return toList().hashCode()
    }

    companion object {
        fun <T> empty(): ImmutableQueue<T> {
            return ImmutableQueue<T>(ImmutableStack.Companion.empty<T>(), ImmutableStack.Companion.empty<T>())
        }
    }
}
